#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print(int *a, int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void Swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}

// 冒泡排序
void BubbleSort(int *a, int size)
{
    for(int i = 0; i < size - 1; i++)   // 要整理的数的最大次数
    {
        int flag = 0;
        for(int j = 0; j < size - i - 1; j++)   // 单轮冒泡比较的次数
        {
            if(a[j] > a[j+1])
            {
                flag = 1;
                Swap(&a[j], &a[j+1]);
            }
        }
        if(flag == 0)   //遍历数列没有任何两个数需要交换，说明已经有序
        {
            break;
        }
    }
}

// 插入排序（要背！！！）
void InsertSort(int *a, int size)
{
    for(int i = 0; i < size; i++)   // 插入的数据个数
    {
        int j = i;  // i是要插入的数据的下标
        int temp = a[i];
        for(; j > 0; j--)
        {
            if(a[j-1] > temp)
                a[j] = a[j-1];  // 比要插入的数大的数就往后挪
            else
                break;
        }
        a[j] = temp; 
    }
}

// 选择排序
#if 0
    void ChooseSort(int *a, int size)
    {
        for(int i = 0; i < size - 1; i++)
        {
            int min = i;
            for(int j = i + 1; j < size; j++)
            {
                if(a[min] > a[j])
                {
                    min = j;
                }
            }
            Swap(&a[i], &a[min]);
        }
    }
#endif

#if 1
    // 双指针算法
    void ChooseSor2(int *a, int size)
    {
        for(int left = 0, right = size - 1; left < right; left++, right--)
        {
           int min = left, max = right;
           for(int i = left; i <= right; i++)
           {
                if(a[min] > a[i])
                {
                    min = i;
                }
                if(a[max] < a[i])
                {
                    max = i;
                }
           }
           Swap(&a[left], &a[min]);
           // 极值正好都在两边
           if(max == left)
           {
                max = min;
           }
           Swap(&a[right], &a[max]);
        }
    }
#endif

// 快速排序：双指针 分治 递归（要背！！！）
void FastSort(int *a, int start, int end)
{
    // 终止条件
    if(start >= end)
        return;

    int left = start;
    int right = end;
    int temp = a[left];

    while(left < right)
    {
        // 先从右边动 找比基准值小的数
        while(a[right] > temp && left < right)
            right--;
        // 把右边的值赋给左边的空位 
        if(left < right)
            a[left++] = a[right];
        // 左边动 找比基准值大的数
        while(a[left] < temp && left < right)
            left++;
        // 把左边的值赋给右边的空位
        if(left < right)
            a[right--] = a[left];
    }
    // 基准值给到这个位置
    a[left] = temp;
    // 递归排序
    FastSort(a, start, left - 1);
    FastSort(a, right + 1, end);
}

// 二分查找（要背！！！）
int BinarySearch(int *a, int size, int element)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        // int mid = left + (right - left) / 2;
        int mid = (left & right) + ((left ^ right) >> 1);
        // 比中间值小
        if(a[mid] > element)
            // 左半边找
            right = mid - 1;
        else if(a[mid] < element)
            // 右半边找
            left = mid + 1;
        else
            // 找着了
            return mid;
    }
    // 没找到
    return -1;
}

int main()
{
#if 0
    int a[5];
    srand(time(NULL));

    for(int i = 0; i < 5; i++)
    {
        a[i] = rand() % 100 + 1;
    }
    print(a, sizeof(a) / sizeof(a[0]));
    //BubbleSort(a, sizeof(a) / sizeof(a[0]));
    //InsertSort(a, sizeof(a) / sizeof(a[0]));
    //ChooseSort(a, sizeof(a) / sizeof(a[0]));
    //ChooseSor2(a, sizeof(a) / sizeof(a[0]));
    FastSort(a, 0, 4);

    print(a, sizeof(a) / sizeof(a[0]));
#endif

#if 1
    int a[5] = {14, 10, 85, 14, 40};
    print(a, sizeof(a) / sizeof(a[0]));
    FastSort(a, 0, 4);
    print(a, sizeof(a) / sizeof(a[0]));

    printf("找到的下标是：%d\n", BinarySearch(a, 5, 40));
#endif

    return 0;
}